package dongshi.daddy.binarysearch;

import java.util.HashSet;
import java.util.Set;

/**
 * 
 * @author dongyunqi
 * @date 2018年12月3日下午4:11:08
 * @description
 */
public class SeachTest {

	public static void main(String[] args) {
		 int[] a = new int[] { 1, 2, 3, 4, 5, 6, 7 };
		 binarySeachTest(a, a.length, 4);
		// int[] a = new int[] { 1, 2, 3, 4, 5, 6, 7 };
		// binarySeachRecursionTest(a, 0, a.length - 1, 7);
		// int[] a = new int[] { 1, 2, 3, 4, 4, 5, 5, 5, 6, 7 };
		// binarySeachFirstWithDup(a, a.length, 5);
		// int[] a = new int[] { 1, 2, 3, 4, 4, 5, 5, 5, 6, 7 };
		// binarySeachLastWithDup(a, a.length, 5);
		// int[] a = new int[] { 1, 2, 3, 4, 4, 5, 5, 5, 6, 7 };
		// binarySeachFistBigOrEqualWithDup(a, a.length, 7);
//		int[] a = new int[] { 1, 2, 3, 4, 4, 5, 5, 5, 6, 7 };
//		binarySeachLastLessOrEqualWithDup(a, a.length, 1);
		binarySearchIpAddrTest();
	}

	public static void binarySearchIpAddrTest() {
		// 模拟IP地址库
		IpRangeAddr[] addrArr = new IpRangeAddr[5]; 
		// 构建IP地址库（这里构建的数据天然按照最小ip有序，可省略排序步骤）
		for (int i = 0; i < addrArr.length; i++) {
			IpRangeAddr newAddr = new IpRangeAddr();
			newAddr.minIp = i * 5 + 1;
			newAddr.maxIp = i * 5 + 5;
			newAddr.addr = "河南新乡" + i;
			Set<Integer> ips = new HashSet<>();
			ips.add(i * 5 + 1);
			ips.add(i * 5 + 2);
			ips.add(i * 5 + 4);
			ips.add(i * 5 + 5);
			newAddr.ips = ips;
			addrArr[i] = newAddr;
		}
		binarySeachLastLessOrEqualWithDup(addrArr, addrArr.length, 24);
	}

	// 查询最后一个小于等于给定值的元素
	public static int binarySeachLastLessOrEqualWithDup(IpRangeAddr[] a, int n, int value) {
		int low = 0;
		int high = n - 1;
		while (low <= high) {
			// 获取中间值
			int middle = (low + high) / 2;
			// 如果当前中间值等于目标值则直接返回
			// 若大于则继续向左二分，否则继续向右二分
			if (a[middle].minIp <= value) {
				if (middle == n - 1 || a[middle + 1].minIp > value) {
					if (a[middle].ips.contains(value)) {
						System.out.println("存在重复元素二分查找非递归版本-要查找元素索引为：" + middle + ",地址为：" + a[middle].addr);
						return middle;
					} else {
						System.out.println("目标ip不存在");
						return middle;
					}
				} else {
					low = middle + 1;
				}
			} else if (a[middle].minIp > value) {
				high = middle - 1;
			}
		}
		System.out.println("目标ip不存在");
		return -1;
	}

	
	// 查询最后一个小于等于给定值的元素
	public static int binarySeachLastLessOrEqualWithDup(int[] a, int n, int value) {
		int low = 0;
		int high = n - 1;
		while (low <= high) {
			// 获取中间值
			int middle = (low + high) / 2;
			// 如果当前中间值等于目标值则直接返回
			// 若大于则继续向左二分，否则继续向右二分
			if (a[middle] <= value) {
				if (middle == n - 1 || a[middle + 1] > value) {
					System.out.println("存在重复元素二分查找非递归版本-要查找元素索引为：" + middle + ",值为：" + a[middle]);
					return middle;
				} else {
					low = middle + 1;
				}
			}  else if (a[middle] > value) {
				high = middle - 1;
			}
		}
		System.out.println("存在重复元素二分查找非递归版本-不存在该元素");
		return -1;
	}

	// 查询第一个大于等于给定值的元素
	public static int binarySeachFistBigOrEqualWithDup(int[] a, int n, int value) {
		int low = 0;
		int high = n - 1;
		while (low <= high) {
			// 获取中间值
			int middle = (low + high) / 2;
			// 如果当前中间值等于目标值则直接返回
			// 若大于则继续向左二分，否则继续向右二分
			if (a[middle] >= value) {
				if (middle == 0 || a[middle - 1] < value) {
					System.out.println("存在重复元素二分查找非递归版本-要查找元素索引为：" + middle + ",值为：" + a[middle]);
					return middle;
				} else {
					high = middle - 1;
				}
			} else if (a[middle] < value) {
				low = middle + 1;
			}
		}
		System.out.println("存在重复元素二分查找非递归版本-不存在该元素");
		return -1;
	}

	// 存在重复元素时，查找最后一个符合的元素
	public static int binarySeachLastWithDup(int[] a, int n, int value) {
		int low = 0;
		int high = n - 1;
		while (low <= high) {
			// 获取中间值
			int middle = (low + high) / 2;
			// 如果当前中间值等于目标值则直接返回
			// 若大于则继续向左二分，否则继续向右二分
			if (a[middle] == value) {
				if (middle == n - 1 || a[middle + 1] != value) {
					System.out.println("存在重复元素二分查找非递归版本-要查找元素索引为：" + middle + ",值为：" + a[middle]);
					return middle;
				} else {
					high = middle - 1;
				}
			} else if (a[middle] < value) {
				low = middle + 1;
			} else if (a[middle] > value) {
				high = middle - 1;
			}
		}
		System.out.println("存在重复元素二分查找非递归版本-不存在该元素");
		return -1;
	}

	// 存在重复元素时，查找第一个符合的元素
	public static int binarySeachFirstWithDup(int[] a, int n, int value) {
		int low = 0;
		int high = n - 1;
		while (low <= high) {
			// 获取中间值
			int middle = (low + high) / 2;
			// 如果当前中间值等于目标值则直接返回
			// 若大于则继续向左二分，否则继续向右二分
			if (a[middle] == value) {
				// 如果该元素是第一个元素或者上一个元素不是要找的元素
				// 则该元素就是要找的首个元素
				// 否则前面还有继续向前
				if (middle == 0 || a[middle - 1] != value) {
					System.out.println("存在重复元素二分查找非递归版本-要查找元素索引为：" + middle + ",值为：" + a[middle]);
					return middle;
				} else {
					high = middle - 1;
				}
			} else if (a[middle] < value) {
				low = middle + 1;
			} else if (a[middle] > value) {
				high = middle - 1;
			}
		}
		System.out.println("存在重复元素二分查找非递归版本-不存在该元素");
		return -1;
	}

	// 有效数据组中不存在重复元素的递归版本
	// 终止条件 low<high
	// 递推条件bS(arr,low,high)=bS(arr,(low+high)/2+1,high)||bS(arr,low,(low+high)/2-1)
	public static int binarySeachRecursionTest(int[] a, int low, int high, int value) {
		// 写终止条件
		if (high < low) {
			System.out.println("二分查找递归版本-不存在该元素");
			return -1;
		}
		// 获取中间值
		int middle = (low + high) / 2;
		// 如果当前中间值等于目标值则直接返回
		// 若大于则继续向左二分，否则继续向右二分
		if (a[middle] == value) {
			System.out.println("二分查找非递归版本-要查找元素索引为：" + middle + ",值为：" + a[middle]);
			return middle;
		} else if (a[middle] < value) {
			binarySeachRecursionTest(a, middle + 1, high, value);
		} else if (a[middle] > value) {
			binarySeachRecursionTest(a, low, middle - 1, value);
		}
		return -1;
	}

	// 有效数据组中不存在重复元素的非递归版本
	public static int binarySeachTest(int[] a, int n, int value) {
		int low = 0;
		int high = n - 1;
		while (low <= high) {
			// 获取中间值
			int middle = (low + high) / 2;
			// 如果当前中间值等于目标值则直接返回
			// 若大于则继续向左二分，否则继续向右二分
			if (a[middle] == value) {
				System.out.println("二分查找非递归版本-要查找元素索引为：" + middle + ",值为：" + a[middle]);
				return middle;
			} else if (a[middle] < value) {
				low = middle + 1;
			} else if (a[middle] > value) {
				high = middle - 1;
			}
		}
		System.out.println("二分查找非递归版本-不存在该元素");
		return -1;
	}
}
